| Stefan Staiger
| creator |
Staiger, Stefan
| | date |
2005-10-06
| | | | description |
123 pages
| |
Die Diplomarbeit ist eine Ausarbeitung und Weiterführung der
aktuellen Forschung von Neeraj Kayal und Nitin Saxena. Diese haben
das algorithmische Studium von Fragen rund um Ringe begonnen. Die
Diplomarbeit präsentiert die hierbei entstandenen Algorithmen und
komplexitätstheoretischen Überlegungen in ausführlicher und
verständlicher Weise. Behandelt werden beispielsweise die Fragen,
ob zwei Ringe isomorph sind, wie viele Automorphismen sie haben und
wie man Iso- und Automorphismen berechnen kann. Hierzu werden eine
Reihe mathematischer Grundlagen erläutert.
Darüber hinaus leitet die Diplomarbeit neue Ergebnisse zu endlichen
Ringen her und korrigiert einen Fehler von Kayal und Saxena. Ferner
werden die Ring-Probleme in Beziehung gesetzt zu den bekannten
Problemen der Graph-Isomorphie und des Faktorisierens großer
Zahlen. Die Arbeit präsentiert außerdem einen Überblick über die
aktuellen Faktorisierungsverfahren und schließt mit einer Reihe
noch offener Fragen, die als Grundlage für weitere Forschung dienen
können.
Englisch:
The diploma thesis presents and continues the current research of
Neeraj Kayal and Nitin Saxena. They started studying algorithmic
problems around rings. The diploma thesis presents the algorithms
and insights achieved in a detailed and understandable manner. For
example, topics like counting ring iso- and automorphisms and the
ring isomorphism problem are covered. For that, we explain the
mathematical basics needed to understand the ideas.
Furthermore, the diploma thesis proofs new results for finite rings
and corrects an error of Kayal and Saxena. Also, some connections
between the ring problems and the well-known problems of graph
isomorphism and factoring large numbers are shown. The work gives an
overview of the algorithms currently used for factoring numbers and
presents some open questions that might be used as a starting point
for future research.
| | format |
application/pdf
| | 1041025 Bytes | |